题解 CF1009E 【Intercity Travelling】

发表于 | 更新于

$Description$

你要从$A$到$B$，需要走$n$步。若你已走了$s$步，那么你再走一步的代价将为$a[s+1]$。

在走完每一步后有$\frac{1}{2}$的概率休息，休息后$s$将变为$0$。

求出你从$A$到$B$的代价的期望$p$乘上$2^{n-1}$对$998244353$取模的结果。

$Solution$

由于乘了$2^{n-1},$所以答案即是所有情况走的代价之和

考虑一个复杂度为$O(n^2)$的$dp,$设$f[i]$表示走了$i$步后的答案。

显然，$f[i]=\sum\limits_{i=1}^{i-1}(f[j]+2^{j-1}\times sum_{i-j})+sum_i$

然后发现这个式子很难优化所以对它进行推导

$f[i]=\sum\limits_{j=1}^{i-1}(f[j]+2^{j-1}\times sum[i-j])+sum[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+[\sum\limits_{j=1}^{i-1}(2^{j-1}\times sum_[i-j])]+sum[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+[\sum\limits_{j=1}^{i-1}(sum[j]\times2^{i-1-j})]+sum[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+[\sum\limits_{j=1}^{i-1}(a[i]\times\sum\limits_{k=0}^{i-1-j}2^k)]+sum[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+\sum\limits_{j=1}^{i-1}[a[i]\times (2^{i-j}-1)]+sum[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+\sum\limits_{j=1}^{i-1}[a[i]\times 2^{i-j}]-sum[i-1]+sum[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+\sum\limits_{j=1}^{i-1}[a[i]\times 2^{i-j}]+a[i]$

$f[i]=(\sum\limits_{j=1}^{i-1}f[j])+\sum\limits_{j=1}^{i}[a[i]\times 2^{i-j}]$

设$g[i]=\sum\limits_{j=1}^{i-1}f[j],h[i]=\sum\limits_{j=1}^{i}[a[i]\times 2^{i-j}]$

$g[i]=g[i-1]+f[i],h[i]=h[i-1]\times 2+a[i]$

然后就可以无脑递推了

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 1000007
#define mod 998244353
using namespace std;

inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int n,x,h,f,g;
signed main(){
    n=read();
    for (int i=1;i<=n;++i){
        x=read();
        h=((h<<1)+x)%mod;f=(g+h)%mod;g=(g+f)%mod;
    }
    printf("%d\n",f);
    return 0;
}